#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1005;
string s[N];
int n,t;

int main(){
    freopen("brotherhood.in","r",stdin);
    freopen("brotherhood.out","w",stdout);
    cin >> n >> t;
    s[1] = "0",s[2] = "1";
    for(int k=3;k<=n;k++)
        s[k] = s[k-1]+s[k-2];
    while(t--){
        string c;
        cin >> c;
        int ans = 0;
        for(int k=0;k<=(int)(s[n].size()-c.size());k++)
            if(s[n].substr(k,c.size())==c)
                ans++;
        cout << ans << endl;
    }
    return 0;
}